package treeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 层序遍历
 */
public class TreeNodeTop {
    public List<List<Integer>> levelOrderTop(TreeNode root){
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode treeNode =   queue.poll();  //Retrieves and removes the head (first element) of this list
                level.add(treeNode.val);
                TreeNode left = treeNode.left;
                TreeNode right = treeNode.right;
                if(left!=null){
                    queue.offer(left);
                }
                if(right!=null){
                    queue.offer(right);
                }
            }
            levelOrder.add(level);
        }


        return levelOrder;
    }

    public static void main(String[] args) {
        TreeNodeTop test= new TreeNodeTop();
        List<List<Integer>> list = test.levelOrderTop(TreeNodeUtils.getTestTreeNode());
        for (List<Integer> item:list){
            System.out.println(item);
        }
    }
}
